package listbyorder.access001_100.test22;

import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/5/29 14:00
 */
public class Solution1 {

    // 递归
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n <= 0) return res;
        getAns(new char[n * 2], 0, res);
        return res;
    }

    private void getAns(char[] chars, int cur, List<String> res) {
        if (cur == chars.length) {
            if (isVilid(chars)) {
                res.add(new String(chars));
            }
        } else {
            chars[cur] = '(';
            getAns(chars, cur + 1, res);
            chars[cur] = ')';
            getAns(chars, cur + 1, res);
        }
    }

    private boolean isVilid(char[] chars) {
        int count = 0;
        for (char c : chars) {
            if (c == '(') {
                count++;
            } else {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }
}
